This invention relates to random number generation and more particularly to a random number generator using a chaotic circuit. Random and pseudo-random numbers are used for purposes such as test-data generation, Monte-Carlo simulation techniques, generation of spreading sequences for spread spectrum communications and cryptography. The applications place constraints on how random numbers are generated. A main design criterion is whether the sequence needs to be repeatable. Repeatable pseudo-random number generators are implemented in digital hardware or software. As used herein a pseudo-random number generator refers to a deterministic device which generates a nonrepeatable sequence of numbers, and not merely a device which generates a repeatable sequence which satisfies selected criteria of random behavior.
The security of a pseudo-random number generator, particularly a repeatable generator, is of paramount importance to the field of cryptography, where it is equivalent to the problem of finding a secure encryption method. The security of a pseudo-random or random number generator is a measure of how difficult it is to predict future values of the sequence based on past values of a sequence. The level of difficulty may be defined in computational or probabilistic terms depending on the type of generator.
For the present application, repeatability is not necessary and in fact is to be avoided, but security is a major concern. The present application includes key generation, which is used in cryptography, and various aspects of key management. Typically, such applications sample noise from reverse-biased diodes, oscillator phase noise or other physical phenomena. However, due to the difficulties encountered in dealing with diode noise sources (which are inherently bandlimited and have undesired aging and thermal characteristics), as well as other natural sources of noise, alternative deterministic circuits have been developed. However, deterministic generators, such as described by Letham et al., "A 128K EPROM Using Encryption of Pseudorandom Numbers to Enable Read Access," IEEE Journal of Solid State Circuits, Vol. SC-21, No. 5, pp. 881-888 (October 1986), are difficult to deal with because of the difficulty of determining whether the sequence is sufficiently random and secure and whether such circuits are easier to implement than smaller circuits that serve the same purpose.
In recent years a new science has developed in the field of nonlinear dynamics, more generally known as chaos. The nonlinear phenomenon of chaos poses a promising deterministic alternative for pseudo-random number generation due to its characteristic unpredictable behavior. Chaos, in fact, produces unpredictable behavior in a fairly predictable manner.
The application of chaos to number generation has been suggested in the past. In Tang et al., "Synchronization and Chaos," IEEE Transactions on Circuits and Systems, Vol. CAS-30 (September 1983), it was noted that there is a similarity between a map approximating a nonlinear forced oscillator and a map describing a linear congruential pseudo-random number generator. In Oishi et al., "Pseudo-Random Number Generators and Chaos," The Transactions of the IECE of Japan, Vol. E 65 (September 1982), it was shown how to use chaotic first-order difference equations to generate pseudo-random sequences with a prescribed distribution function. However, the security and predictability issue was not addressed.
The information loss properties of a chaotic system were first described by Shaw in "Strange Attractors, Chaotic Behavior and Information Flow," Z. Naturforschung, Vol. 36a, pp. 80-112 (1981). This important work showed the relationship between information and chaos, but it made no suggestion about potential applications, particularly in the field of key generation and management.
In G. M. Bernstein, Nonlinear Oscillations, Synchronization and Chaos, Ph.D. thesis, University of California-Berkeley (March 1988), there is mention of the potential use of chaotic circuits in security applications. However, there was no mechanism suggested therein for mathematically justifying the level of security of chaotic behavior of nonlinear circuitry. Such justification is necessary in order to determine the level of security attained.
What is needed is a method for generating a measurably secure, nonrepeatable pseudo-random number for applications requiring a random number.
The following patents were uncovered in a search of the records of the U.S. Patent and Trademark Office: U.S. Pat. No. 4,545,024 describes a hybrid natural random number generator which requires the use of a white-noise source, namely, a band-limited, stationary, white Gaussian noise signal such as that which is available from a number of commercial noise diodes. It is known that noise-diode statistical properties tend to change with age, which can degrade the security of a device using such a generator. In addition, the use of a noise diode requires at least one component to be added to the circuit which is not adapted to integration into a single integrated circuit.
U.S. Pat. No. 4,769,777 describes an unpredictable bit stream generator using a scheme of linear shift registers and number generators to produce random bits from pseudo-random bits. This is an alternative approach which represents a substantially greater complication than is required of the present invention.
U.S. Pat. No. 4,799,259 describes a monolithic random digital noise generator involving a collection of oscillators at incommensurate frequencies, i.e., frequencies which are not related by a rational number. The predictability of this generator is not analyzed, and it can be shown that the random digital noise generator would be predictable if the initial frequencies and phases of the oscillators were known to a reasonable precision. The circuit described therein has a different theoretical basis than the present invention.
U.S. Pat. No. 4,810,975 describes a random number generator using sampled output of a variable-frequency oscillator. The invention described therein is similar to the foregoing, but it is subject to a different explanation of operation. The circuit used therein is a triangle wave oscillator used to frequency modulate a second oscillator, which then produces a complicated waveform, which is then sampled to produce numbers taken as random numbers. As with the foregoing references, the principle herein is to produce a waveform whose frequency spectrum approximates a band-limited white-noise source which is thereafter sampled. It is subject to the same limitations on security as the foregoing references.
U.S. Pat. No. 4,855,690 describes an integrated circuit random number generator using the sampled output of a variable-frequency oscillator. This is a continuation application of the foregoing '975 patent.
U.S. Pat. No. 4,853,884 describes a random number generator with digital feedback. Therein a noise-diode-based circuit is employed. It has the same drawback as previously identified, namely, the requirement of a separate noise-diode component and bias circuitry. This method is not suitable for integration with other cryptographic functions on a single chip.